Free Solved Question Paper of BCS42 - Introduction to Algorithm Design for Decmeber 2023

1. (a) Show that : $5n^2 + 2n + 2 = \theta(n^2)$ (2 Marks)

Answer:

To prove $5n^2 + 2n + 2 = \theta(n^2)$, we demonstrate both Big O and Omega bounds.
Big O (Upper Bound): For all $n \geq 1$, $5n^2 + 2n + 2 \leq 9n^2$. Thus, $5n^2 + 2n + 2 = O(n^2)$.
Omega (Lower Bound): For all $n \geq 1$, $5n^2 + 2n + 2 \geq 5n^2$. Thus, $5n^2 + 2n + 2 = \Omega(n^2)$.
Therefore, $5n^2 + 2n + 2 = \theta(n^2)$ by definition of Theta notation.

1. (b) Solve the following recurrence relation :
$T(n) = 3T(\frac{n}{2}) + n$

Answer:

To solve the recurrence relation $T(n) = 3T\left(\frac{n}{2}\right) + n$ using the Master Theorem, we will follow the steps outlined in the theorem.

First, we identify the values of $a$, $b$, and $f(n)$:

• $a = 3$
• $b = 2$
• $f(n) = n$

Next, we compare $f(n)$ with $n^{\log_b a}$. For this, we need to calculate $\log_b a$:

$\log_b a = \log_2 3$

Using the properties of logarithms, we find:

$\log_2 3 \approx 1.58496$

Now, we have $f(n) = n$ and we can express $f(n)$ as:

$f(n) = n^1$

Here, $k = 1$.

We compare $\log_b a$ and $k$:

• $\log_b a \approx 1.58496$
• $k = 1$

Since $\log_b a > k$ (because $1.58496 > 1$), this falls under Case 1 of the Master Theorem:

Case 1: If $\log_b a > k$, then $T(n) = \Theta(n^{\log_b a})$.

Thus, the solution to the recurrence relation $T(n) = 3T\left(\frac{n}{2}\right) + n$ is:

$T(n) = \Theta(n^{\log_2 3})$

$T(n) = \Theta(n^{1.58496})$

So, the final answer is:

$T(n) = \Theta(n^{\log_2 3}) \approx \Theta(n^{1.58496})$

1. (c) Write binary search algorithm and explain its best case and worst case complexity. (5 marks)

Answer:

Binary Search Algorithm (Recursive):

def binary_search(arr, target, left, right):
    if left > right:
        return -1  # Target not found

    mid = (left + right) // 2

    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, right)
    else:
        return binary_search(arr, target, left, mid - 1)

# Helper function to start the binary search
def search(arr, target):
    return binary_search(arr, target, 0, len(arr) - 1)
        

Explanation:

The binary search algorithm works by repeatedly dividing the search interval in half. The algorithm begins with an interval covering the entire array. If the target value is less than the value in the middle of the interval, the algorithm narrows the interval to the lower half. Otherwise, it narrows it to the upper half. The process continues until the target value is found or the interval is empty.

Best Case Complexity: The best case occurs when the target element is the middle element of the array. In this case, the algorithm will find the target in constant time: $O(1)$

Worst Case Complexity: The worst case occurs when the algorithm has to divide the array and check elements in every step until the search interval is reduced to a single element. This happens when the target element is not present in the array or is located at the beginning or end of the array. The time complexity in the worst case is logarithmic in terms of the number of elements: $O(\log n)$

1. (d) Represent the following graph using Adjacency List : (4 marks)

Answer:

To represent the given graph using an adjacency list, we list each vertex along with the vertices it is connected to by an edge. The adjacency list representation of the given graph is as follows:

A → B, C, D
B → A, F
C → A, E
D → A, F
E → C, F

1. (e) Sort the following list of elements using quick sort. Also show the steps of the operation : (6 marks)

8, 29, 30, 6, 25, 7, 8, 9

Answer:

Quick Sort Algorithm:

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

# Example usage
arr = [8, 29, 30, 6, 25, 7, 8, 9]
sorted_arr = quick_sort(arr)
print(sorted_arr)
        

Steps of the operation:

Initial list: 8, 29, 30, 6, 25, 7, 8, 9

Step 1: Choose pivot (middle element): 6

→ Left: [], Middle: [6], Right: [8, 29, 30, 25, 7, 8, 9]

Step 2: Recursively apply quick sort on the left and right sublists.

Right list: [8, 29, 30, 25, 7, 8, 9], choose pivot: 25

→ Left: [8, 7, 8, 9], Middle: [25], Right: [29, 30]

Step 3: Recursively apply quick sort on the left and right sublists of [8, 7, 8, 9]

Left list: [8, 7, 8, 9], choose pivot: 8

→ Left: [7], Middle: [8, 8], Right: [9]

Step 4: Recursively apply quick sort on [7] and [9] (both already sorted)

Combining results: [7, 8, 8, 9]

Step 5: Combine all sorted sublists

Final sorted list: [6, 7, 8, 8, 9, 25, 29, 30]

2. (a) Define the following terms : (4 marks)

(i) Connected graph
(ii) Cycle in an undirected graph

Answer:

(i) Connected graph:

A connected graph is a type of graph in which there is a path between every pair of vertices. This means that for any two vertices $u$ and $v$ in the graph, there is a sequence of edges that can be followed to get from $u$ to $v$. In other words, it is possible to reach any vertex from any other vertex in a connected graph.

(ii) Cycle in an undirected graph:

A cycle in an undirected graph is a sequence of vertices starting and ending at the same vertex, with each pair of consecutive vertices being connected by an edge, and no vertex (except the starting/ending vertex) being repeated. Formally, a cycle is a path $v_1, v_2, \ldots, v_k$ such that $v_1 = v_k$ and all $v_i$ for $1 \leq i < k$ are distinct.

2. (b) Write Euclid’s algorithm for finding GCD and explain it. (6 marks)

Answer:

Euclid's Algorithm for Finding GCD:

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// Example usage
int result = gcd(48, 18);
cout << result;  // Output: 6
        

Explanation:

Euclid's algorithm is a method for finding the Greatest Common Divisor (GCD) of two integers. The GCD of two numbers is the largest number that divides both of them without leaving a remainder. The algorithm is based on the principle that the GCD of two numbers also divides their difference.

The steps of the algorithm are as follows:

→ Step 1: Start with two numbers, $a$ and $b$.

→ Step 2: Check if $b$ is 0. If it is, the GCD is $a$.

→ Step 3: If $b$ is not 0, replace $a$ with $b$ and $b$ with $a \mod b$.

→ Step 4: Repeat the process until $b$ becomes 0. The value of $a$ at this point is the GCD of the original two numbers.

For example, to find the GCD of 48 and 18:

→ 48 % 18 = 12

→ 18 % 12 = 6

→ 12 % 6 = 0

The GCD is 6.

3. (a) What is spanning tree? Explain application of spanning tree. (4 marks)

Answer:

A spanning tree of a graph is a subgraph that includes all the vertices of the original graph and is a tree (a connected acyclic graph). In simpler terms, it's a way of connecting all the vertices of a graph without creating any cycles and ensuring every vertex is reachable.

1. Definition:
→ A spanning tree of a graph G is a subgraph that contains all the vertices of G .
→ It must be a tree, meaning it is acyclic (no cycles) and connected (there's a path between any pair of vertices).

2. Construction:
→ To construct a spanning tree, we start with any vertex and add edges to connect more vertices without forming cycles until all vertices are included.

3. Properties:
→ For a graph with n vertices, a spanning tree will always have n-1 edges.
→ It ensures that there is exactly one path between any pair of vertices, making it useful for communication and network design.

Applications:

→ Network Design: In computer networks, spanning trees are used to ensure that all nodes can communicate without creating loops (which could lead to data packets endlessly circulating). Spanning tree protocols like STP (Spanning Tree Protocol) are crucial in Ethernet networks.

→ Routing in Networks: Spanning trees help in defining efficient routes between nodes. For example, in a telecommunications network, a spanning tree can guide how messages or calls are routed from one node to another.

→ Graph Theory: In graph theory itself, spanning trees are studied as fundamental structures. Properties and algorithms related to spanning trees are used to analyze graph connectivity and design efficient algorithms.

→ Sensor Networks: In sensor networks, where multiple sensors (nodes) need to communicate data to a central hub (base station), spanning trees can optimize data aggregation and transmission paths.

→ MST (Minimum Spanning Tree): The concept of spanning trees extends to finding the minimum spanning tree, which is the spanning tree with the smallest sum of edge weights. This is particularly important in optimizing costs in network design and resource allocation.

3. (b) Write and explain Dijkstra’s single source shortest path algorithm. (6 marks)

Answer:

Dijkstra's algorithm is a method for finding the shortest paths from a single source vertex to all other vertices in a weighted graph. Here's a detailed explanation:

Algorithm Steps:

1. Initialize a priority queue (or min-heap) to store vertices with their tentative distances from the source.
2. Set the distance to the source vertex as 0 and all other distances as infinity.
3. While the priority queue is not empty:
→ Extract the vertex with the smallest distance (let's call it u).
→ For each neighbor v of u:

• →→If the distance to v through u is shorter than the current known distance, update v's distance.
• →→Update v's entry in the priority queue.
4. Once all vertices have been processed, the distances stored in the priority queue represent the shortest path distances from the source vertex.

Explanation:

Dijkstra's algorithm uses a greedy approach by always selecting the vertex with the smallest known distance to expand next. This ensures that once a vertex's shortest path is found, it is never revisited, guaranteeing optimality.

4. (a) Briefly explain Greedy technique for designing of algorithm. (4 marks)

Answer:

The greedy technique for algorithm design involves making locally optimal choices at each stage with the hope of finding a global optimum solution. Here are key characteristics:

Key Aspects:

• Local Optimal Choice: At each step, a greedy algorithm selects the best possible choice without considering the global picture.
• No Backtracking: Once a decision is made, it is never reconsidered, which can lead to suboptimal solutions in some cases.
• Efficiency: Greedy algorithms are often efficient due to their simple decision-making process, making them suitable for certain types of optimization problems.

Examples:

Examples of greedy algorithms include Dijkstra's algorithm for shortest paths and Kruskal's algorithm for minimum spanning trees. These algorithms demonstrate how locally optimal choices can lead to globally optimal solutions in specific problem domains.

4. (b) Write DFS traversal sequence from the node A for the graph : (6 marks)

Answer:

To find the DFS traversal sequence starting from node A for the given graph, we follow the steps of the Depth-First Search algorithm:

1. Start at node A.
2. Visit an adjacent node that has not been visited yet.
3. Continue visiting adjacent nodes recursively until all nodes are visited.

Let's perform the DFS traversal:

→ Start at A.
→ Move to B (adjacent to A).
→ Move to C (adjacent to B).
→ Move to D (adjacent to C).
→ Backtrack to C (since D has no unvisited adjacent nodes).
→ Move to F (adjacent to C).
→ Move to E (adjacent to B).
→ Backtrack to A (since E has no unvisited adjacent nodes).

Therefore, the DFS traversal sequence starting from node A is:

A, B, C, D, F, E

5. (a) Using mathematical induction method, show that for all positive integers n: (5 marks)
$1 + 2 + 3 + \ldots + n = \frac{n(n + 1)}{2}$

Answer:

We will prove the statement by mathematical induction.

Base Case:

For $n = 1$:

$1 = \frac{1(1 + 1)}{2} = \frac{2}{2} = 1$

The base case holds true.

Inductive Step:

Assume the statement is true for some positive integer $k$, i.e.,

$1 + 2 + 3 + \ldots + k = \frac{k(k + 1)}{2}$

We need to show that the statement holds for $k + 1$, i.e.,

$1 + 2 + 3 + \ldots + k + (k + 1) = \frac{(k + 1)(k + 2)}{2}$

Starting from the inductive hypothesis:

$1 + 2 + 3 + \ldots + k + (k + 1)$

$= \frac{k(k + 1)}{2} + (k + 1)$

$= \frac{k(k + 1) + 2(k + 1)}{2}$

$= \frac{(k + 1)(k + 2)}{2}$

Thus, the statement is true for $k + 1$.

By the principle of mathematical induction, the statement is true for all positive integers $n$.

5. (b) Write Prim’s algorithm for finding minimum spanning tree and find the complexity of this algorithm. (5 marks)

Answer:

Prim's Algorithm:

Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. Here are the steps:

→ Step 1: Initialize a tree with a single vertex, chosen arbitrarily from the graph.

→ Step 2: Grow the tree by one edge: of the edges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, and transfer the vertex at the other end of that edge to the tree.

→ Step 3: Repeat Step 2 until all vertices are in the tree.

Algorithm Complexity:

The time complexity of Prim's algorithm depends on the data structures used:

• If a simple binary heap is used, the complexity is $O(E \log V)$.
• If a Fibonacci heap is used, the complexity is $O(E + \log V)$.